/// [Consecutive prime sum](https://projecteuler.net/problem=50)
fn main() {
    println!("{}", consecutive_prime_sum(1_000_000));
}

fn consecutive_prime_sum(max: usize) -> usize {
    let prime_list = get_prime_list(max);
    let max = prime_list[prime_list.len() - 1];
    let (mut max_sum, mut max_len) = (prime_list[0], 1);
    for i in 0..(prime_list.len() - 1) {
        let mut sum = prime_list[i];
        for j in (i + 1)..prime_list.len() {
            sum += prime_list[j];
            let len = j - i + 1;
            if sum > max_sum && len > max_len && is_prime(sum, &prime_list) {
                max_sum = sum;
                max_len = len;
                println!("{:?}: {}", &prime_list[i..(i + max_len)], max_sum);
            }
            if sum >= max {
                break;
            }
        }
    }
    max_sum
}

fn get_prime_list(max: usize) -> Vec<usize> {
    let mut stat = vec![true; max];
    stat[0] = false;
    for i in 1..max {
        if stat[i] {
            let i = i + 1;
            for j in 2..=(max / i) {
                stat[i * j - 1] = false;
            }
        }
    }
    stat.iter()
        .enumerate()
        .filter(|(_, &s)| s)
        .map(|(i, _)| i + 1)
        .collect()
}

fn is_prime(n: usize, list: &Vec<usize>) -> bool {
    let (mut l, mut c, mut r) = (0, list.len() / 2, list.len());
    while list[c] != n {
        if l == c {
            return false;
        }
        if list[c] < n {
            l = c;
        } else {
            r = c;
        }
        c = (l + r) / 2;
    }
    true
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn prime_sum_is_work() {
        assert_eq!(consecutive_prime_sum(100), 41);
        assert_eq!(consecutive_prime_sum(1000), 953);
    }
    #[test]
    fn get_primes_is_work() {
        assert_eq!(get_prime_list(10), vec![2, 3, 5, 7]);
        assert_eq!(get_prime_list(11), vec![2, 3, 5, 7, 11]);
    }
}
